home *** CD-ROM | disk | FTP | other *** search
/ Internet Surfer 2.0 / Internet Surfer 2.0 (Wayzata Technology) (1996).iso / pc / text / mac / faqs.467 < prev    next >
Text File  |  1996-02-12  |  29KB  |  716 lines

  1. Frequently Asked Questions (FAQS);faqs.467
  2.  
  3.  
  4.  
  5.       Release without charge (4)
  6.  
  7.       for FREE
  8.  
  9. 3. Container
  10.  
  11.    A container clue indicates that something is to be put in (or wrapped
  12.    around) something else.  A container is indicated by phrases such as
  13.    eaten by, contains, in, gobbles, etc.  For example:
  14.  
  15.       In Missouri, consumed by fear (7)
  16.  
  17.       for AMONGST (MO = Missouri in ANGST = fear)
  18.  
  19. 4. Hidden Word
  20.  
  21.    A hidden word is a word embedded in another word or words.  It is
  22.    indicated by phrases such as spot in, hides, at the heart of, covers,
  23.    etc.  For example:
  24.  
  25.       Worn spot in paper at typo (5)
  26.  
  27.       for RATTY (find ratty in "paper at typo")
  28.  
  29. 5. Reversal
  30.  
  31.    A reversal is a definition of a word with the letters reversed.  It is
  32.    indicated by words such as back, reversed, up (for down clues), leftward
  33.    (for across clues), etc.  For example:
  34.  
  35.    Egad! Ray entirely reversed the lot of cloth (7)
  36.  
  37.    for YARDAGE ("Egad! Ray" reversed)
  38.  
  39. 6. Homophone
  40.  
  41.    A homophone definition is a definition of a word that sounds the same as
  42.    the answer, but is spelled differently.  A homophone is indicated by
  43.    words such as in audience, I hear, mouthed, verbally, etc.  For example:
  44.  
  45.    Regrets prank, I hear (4)
  46.  
  47.    for RUES (the homophone is RUSE = prank)
  48.  
  49. 7. Charade
  50.  
  51.    In a charade, the pieces of the word are "spelled" out in order.  There
  52.    are no auxiliary words that indicate a charade.  For example:
  53.  
  54.    Excite a jerk extremist (7)
  55.  
  56.    for FANATIC (FAN = excite, A, TIC = jerk)
  57.  
  58. 8. Deletion
  59.  
  60.    A deletion is a clue where you are instructed to remove a part of some
  61.    word to make another word.  For example,
  62.  
  63.    Times with poor wages (4)
  64.  
  65.    for AGES (with-poor WAGES, where with is abbreviated by W)
  66.  
  67. Often the clue types are combined.  Some common examples are 1) hidden word
  68. reversals where the answer is found backwards embedded in other words, and
  69. 2) containers or charades where the parts are anagrams.  For example:
  70.  
  71.    Car shops have broken gear immersed in gasoline. (7)
  72.  
  73.    for GARAGES (RAGE = gear anagram in GAS = gasoline)
  74.  
  75. All manner of common abbreviations, acronyms, and other symbology such as
  76. roman numerals are allowed.  For example:
  77.  
  78.    c    one hundred, cup, or centigrade
  79.    vi    six
  80.    h    hot
  81.    s    small
  82.    ca    california
  83.  
  84. Two punctuation marks at the end of the clue have been reserved for special
  85. meaning.  A question mark (?) indicates that the straight clue is not
  86. entirely straight (usually a pun).  For example:
  87.  
  88.    I tie down mascara holder soundly? (7)
  89.  
  90.    for EYELASH (homophone of "I lash", mascara holder is a punning
  91.       definition of EYELASH)
  92.  
  93. An exclamation point (!) indicates that some part (usually all) of the clue
  94. overlaps.  For example, the straight definition may also be the anagram
  95. indicator.  Here is an example that entirely overlaps:
  96.  
  97.    A moped also has these! (6)
  98.  
  99.    for PEDALS (hidden word)
  100.  
  101. Here, the entire clue indicates the hidden word, but the entire clue is
  102. also a straight definition of the answer.
  103.  
  104. Give it a try!  Cryptic crossword puzzles are a lot of fun.
  105.  
  106. -- Steve Koehler
  107.    ucsd.edu!telesoft!koehler
  108.    telesoft!koehler@ucsd.edu
  109.    koehler@telesoft.com
  110.  
  111. ==> games/go-moku.p <==
  112. For a game of k in a row on an n x n board,  for what values of k and n is
  113. there a win?  Is (the largest such) k eventually constant or does it increase
  114. with n?
  115.  
  116. ==> games/go-moku.s <==
  117. Berlekamp, Conway, and Guy's _Winning_Ways_ reports proof that the
  118. maximum k is between 4 and 7 inclusive, and it appears to be 5 or 6.
  119. They report:
  120.  
  121. . 4-in-a-row is a draw on a 5x5 board (C. Y. Lee), but not on a 4x30
  122.     board (C. Lustenberger).
  123.  
  124. . N-in-a-row is shown to be a draw on a NxN board for N>4, using a
  125.     general pairing technique devised by A. W. Hales and R. I. Jewett.
  126.  
  127. . 9-in-a-row is a draw even on an infinite board, a 1954 result of H. O.
  128.     Pollak and C. E. Shannon.
  129.  
  130. . More recently, the pseudonymous group T. G. L. Zetters showed that
  131.     8-in-a-row is a draw on an infinite board, and have made some
  132.     progress on showing infinite 7-in-a-row to be a draw.
  133.  
  134. Go-moku is 5-in-a-row played on a 19x19 go board.  It is apparently a
  135. win for the first player, and so the Japanese have introduced several
  136. 'handicaps' for the first player (e.g., he must win with _exactly_
  137. five: 6-in-a-row doesn't count), but apparently the game is still a win
  138. for the first player.  None of these apparent results have been
  139. proven.
  140.  
  141. ==> games/hi-q.p <==
  142. What is the quickest solution of the game Hi-Q (also called Solitair)?
  143.  
  144. For those of you who aren't sure what the game looks like:
  145.  
  146. 32 movable pegs ("+") are arranged on the following board such that
  147. only the middle position is empty ("-"). Just to be complete: the board
  148. consists of only these 33 positions.
  149.  
  150.       1 2 3 4 5 6 7
  151.     1     + + +
  152.     2     + + +
  153.     3 + + + + + + +
  154.     4 + + + - + + +
  155.     5 + + + + + + +
  156.     6     + + +
  157.     7     + + +
  158.  
  159. A piece moves on this board by jumping over one of its immediate
  160. neighboor (horizontally or vertically) into an empty space opposite.
  161. The peg that was jumped over, is hit and removed from the board.  A
  162. move can contain multiple hits if you use the same peg to make the
  163. hits.
  164.  
  165. You have to end with one peg exactly in the middle position (44).
  166.  
  167. ==> games/hi-q.s <==
  168. 1:    46*44
  169. 2:    65*45
  170. 3:    57*55
  171. 4:    54*56
  172. 5:    52*54
  173. 6:    73*53
  174. 7:    43*63
  175. 8:    75*73*53
  176. 9:    35*55
  177. 10:    15*35
  178. 11:    23*43*63*65*45*25
  179. 12:    37*57*55*53
  180. 13:    31*33
  181. 14:    34*32
  182. 15:    51*31*33
  183. 16:    13*15*35
  184. 17:    36*34*32*52*54*34
  185. 18:    24*44
  186.  
  187. Found by Ernest Bergholt in 1912 and was proved to be minimal by John Beasley
  188. in 1964.
  189.  
  190. References
  191.     The Ins and Outs of Peg Solitaire
  192.     John D Beasley
  193.     Oxford U press, 1985
  194.     ISBN 0-19-853203-2
  195.  
  196.     Winning Ways, Vol. 2, Ch. 23
  197.     Berlekamp, E.R.
  198.     Academic Press, 1982
  199.     ISBN 01-12-091102-7
  200.  
  201. ==> games/jeopardy.p <==
  202. What are the highest, lowest, and most different scores contestants
  203. can achieve during a single game of Jeopardy?
  204.  
  205. ==> games/jeopardy.s <==
  206. highest: $283,200.00, lowest: -$29,000.00, biggest difference: $309,700.00
  207.  
  208. (1) Our theoretical contestant has an itchy trigger finger, and rings in with
  209.     an answer before either of his/her opponents.
  210.  
  211. (2) The daily doubles (1 in the Jeopardy! round, 2 in the Double Jeopardy!
  212.     round) all appear under an answer in the $100 or $200 rows.
  213.  
  214. (3) All answers given by our contestant are (will be?) correct.
  215.  
  216. Therefore:
  217.  
  218. Round 1 (Jeopardy!): Max. score per category: $1500.
  219.              For 6 categories - $100 for the DD, that's $8900.
  220.              Our hero bets the farm and wins - score: $17,800.
  221.  
  222. Round 2 (Double Jeopardy!):
  223.              Max. score per category: $3000.
  224.              Assume that the DDs are found last, in order.
  225.              For 6 categories - $400 for both DDs, that's $17,600.
  226.              Added to his/her winnings in Round 1, that's $35,400.
  227.              After the 1st DD, where the whole thing is wagered,
  228.              the contestant's score is $70,800.  Then the whole
  229.              amount is wagered again, yielding a total of $141,600.
  230.  
  231. Round 3 (Final Jeopardy!):
  232.              Our (very greedy! :) hero now bets the whole thing, to
  233.              see just how much s/he can actually win.  Assuming that
  234.              his/her answer is right, the final amount would be
  235.              $283,200.
  236.  
  237. But the contestant can only take home $100,000; the rest is donated to
  238. charity.
  239.  
  240. To calculate the lowest possible socre:
  241.  
  242. -1500 x 6 = -9000 + 100 = -8900.
  243.  
  244. On the Daily Double that appears in the 100 slot, you bet the maximum
  245. allowed, 500, and lose. So after the first round, you are at -9400.
  246.  
  247. -3000 x 6 = -18000 + 400 = -17600
  248.  
  249. On the two Daily Doubles in the 200 slots, bet the maximum allowed, 1000. So
  250. after the second round you are at -9400 + -19600 = -29000. This is the
  251. lowest score you can achieve in Jeopardy before the Final Jeopardy round.
  252.  
  253. The caveat here is that you *must* be the person sitting in the left-most
  254. seat (either a returning champion or the luckier of the three people who
  255. come in after a five-time champion "retires") at the beginning of the game,
  256. because otherwise you will not have control of the board when the first
  257. Daily Double comes along.
  258.  
  259. ==> games/knight.tour.p <==
  260. For what board sizes is a knight's tour possible?
  261.  
  262. ==> games/knight.tour.s <==
  263. A tour exists for boards of size 1x1, 3x4, 3xN with N >= 7, 4xN with N >= 5,
  264. and MxN with N >= M >= 5.  In other words, for all rectangles except 1xN
  265. (excluding the trivial 1x1), 2xN, 3x3, 3x5, 3x6, 4x4.
  266.  
  267. With the exception of 3x8 and 4xN, any even-sized board which allows a tour
  268. will also allow a closed (reentrant) tour.
  269.  
  270. On an odd-sided board, there is one more square of one color than
  271. of the other.  Every time a knight moves, it moves to a square of
  272. the other color than the one it is on.  Therefore, on an odd-sided
  273. board, it must end the last move but one of the complete, reentrant
  274. tour on a square of the same color as that on which it started.
  275. It is then impossible to make the last move, for that move would end
  276. on a square of the same color as it begins on.
  277.  
  278. Here is a solution for the 7x7 board (which is not reentrant).
  279.      ------------------------------------
  280.      | 17 |  6 | 33 | 42 | 15 |  4 | 25 |
  281.      ------------------------------------
  282.      | 32 | 47 | 16 |  5 | 26 | 35 | 14 |
  283.      ------------------------------------
  284.      |  7 | 18 | 43 | 34 | 41 | 24 |  3 |
  285.      ------------------------------------
  286.      | 46 | 31 | 48 | 27 | 44 | 13 | 36 |
  287.      ------------------------------------
  288.      | 19 |  8 | 45 | 40 | 49 |  2 | 23 |
  289.      ------------------------------------
  290.      | 30 | 39 | 10 | 21 | 28 | 37 | 12 |
  291.      ------------------------------------
  292.      |  9 | 20 | 29 | 38 | 11 | 22 |  1 |
  293.      ------------------------------------
  294.  
  295. Here is a solution for the 5x5 board (which is not reentrant).
  296.      --------------------------
  297.      |  5 | 10 | 15 | 20 |  3 |
  298.      --------------------------
  299.      | 16 | 21 |  4 |  9 | 14 |
  300.      --------------------------
  301.      | 11 |  6 | 25 |  2 | 19 |
  302.      --------------------------
  303.      | 22 | 17 |  8 | 13 | 24 |
  304.      --------------------------
  305.      |  7 | 12 | 23 | 18 |  1 |
  306.      --------------------------
  307.  
  308. Here is a reentrant 2x4x4 tour:
  309.      0 11 16  3    15  4  1 22
  310.     19 26  9 24     8 23 14 27
  311.     10  5 30 17    31 12 21  2
  312.     29 18 25  6    20  7 28 13
  313. A reentrant 4x4x4 tour can be constructed by splicing two copies.
  314.  
  315. It shouldn't be much more work now to completely solve the problem of which 3D
  316. rectangular boards allow tours.
  317.  
  318. ==> games/nim.p <==
  319. Place 10 piles of 10 $1 bills in a row.  A valid move is to reduce
  320. the last i>0 piles by the same amount j>0 for some i and j; a pile
  321. reduced to nothing is considered to have been removed.  The loser
  322. is the player who picks up the last dollar, and they must forfeit
  323. half of what they picked up to the winner.
  324.  
  325. 1)  Who is the winner in Waldo Nim, the first or the second player?
  326.  
  327. 2)  How much more money than the loser can the winner obtain with best
  328.     play on both parties?
  329.  
  330. ==> games/nim.s <==
  331. For the particular game described we only need to consider positions for
  332. which the following condition holds for each pile:
  333.  
  334.     (number of bills in pile k) + k >= (number of piles) + 1
  335.  
  336. A GOOD position is defined as one in which this condition holds,
  337. with equality applying only to one pile P, and all piles following P
  338. having the same number of bills as P.
  339. ( So the initial position is GOOD, the special pile being the first. )
  340. I now claim that if I leave you a GOOD position, and you make any move,
  341. I can move back to a GOOD position.
  342.  
  343. Suppose there are n piles and the special pile is numbered (n-p+1)
  344. (so that the last p piles each contain p bills).
  345. (1) You take p bills from p or more piles;
  346.   (a) If p = n, you have just taken the last bill and lost.
  347.   (b) Otherwise I reduce pile (n-p) (which is now the last) to 1 bill.
  348. (2) You take p bills from r(<p) piles;
  349.     I take r bills from (p-r) piles.
  350. (3) You take q(<p) bills from p or more piles;
  351.     I take (p-q) bills from q piles.
  352. (4) You take q(<p) bills from r(<p) piles;
  353.   (a) q+r>p; I take (p-q) bills from (q+r-p) piles
  354.   (b) q+r<=p; I take (p-q) bills from (q+r) piles
  355.  
  356. Verifying that each of the resulting positions is GOOD is tedious
  357. but straightforward.  It is left as an exercise for the reader.
  358.  
  359.     -- RobH
  360.  
  361. ==> games/othello.p <==
  362. How good are computers at Othello?
  363.  
  364. ==> games/othello.s <==
  365. The interesting game in which computers are undoubted masters of all they
  366. survey is Othello, where Kai-Fu Lee's (CMU) program "Bill" is so good it can
  367. only play itself to learn to get better.  Bill has a fantastically
  368. correct and efficient evaluation function, that recently has been further
  369. improved by learning coefficients for additional terms made up of the
  370. pair-wise combination of the four old terms.  This improved  the quality
  371. of the play approximately as much as searching an extra two ply.
  372.  
  373. Bill is so good it can beat lots of players with no search at all.  Its
  374. 6 or 7 ply search sweeps aside all opposition (though Kai-Fu says that some
  375. very good players are now coming along in Japan, and he is not sure whether
  376. Bill would beat them).  One interesting question remaining in Othello is
  377. the game theoretic value of the starting position.  Bill's results seem
  378. to indicate that the first player has an advantage.  It appears that,
  379. since Kai-Fu has published all his evaluation material, someone could
  380. build an Othello machine, and produce a constructive proof (as was done
  381. for Cubic) that it is a win for the first player.
  382.  
  383. ==> games/risk.p <==
  384. What are the odds when tossing dice in Risk?
  385.  
  386. ==> games/risk.s <==
  387. Attacker using 3 dice, Defender using 2:
  388.  
  389.     Probability that Attacker wins 2 = 2323 / 7776
  390.     Probability that Attacker wins 1 = 3724 / 7776
  391.     Probability that Attacker wins 0 = 1729 / 7776
  392.  
  393. Attacker using 3 dice, Defender using 1:
  394.  
  395.     Probability that Attacker wins 1 = 855 / 1296
  396.     Probability that Attacker wins 0 = 441 / 1296
  397.  
  398. Attacker using 2 dice, Defender using 2:
  399.  
  400.     Probability that Attacker wins 2 = 225 / 1296
  401.     Probability that Attacker wins 1 = 630 / 1296
  402.     Probability that Attacker wins 0 = 441 / 1296
  403.  
  404. Attacker using 2 dice, Defender using 1:
  405.  
  406.     Probability that Attacker wins 1 = 125 / 216
  407.     Probability that Attacker wins 0 = 91 / 216
  408.  
  409. Attacker using 1 dice, Defender using 2:
  410.  
  411.     Probability that Attacker wins 1 = 90 / 216
  412.     Probability that Attacker wins 0 = 126 / 216
  413.  
  414. Attacker using 1 dice, Defender using 1:
  415.  
  416.     Probability that Attacker wins 1 = 15 / 36
  417.     Probability that Attacker wins 0 = 21 / 36
  418.  
  419. ==> games/rubiks.clock.p <==
  420. How do you quickly solve Rubik's clock?
  421.  
  422. ==> games/rubiks.clock.s <==
  423.                           Solution to Rubik's Clock
  424.  
  425. The solution to Rubik's Clock is very simple and the clock can be
  426. "worked" in 10-20 seconds once the solution is known.
  427.  
  428. In this description of how to solve the clock I will describe
  429. the different clocks as if they were on a map (e.g. N,NE,E,SE,S,SW,W,NW);
  430. this leaves the middle clock which I will just call M.
  431. To work the Rubik's clock choose one side to start from; it does
  432. not matter from which side you start.  Your initial goal
  433. will be to align the N,S,E,W and M clocks.  Use the following algorithm
  434. to do this:
  435.  
  436.     [1]  Start with all buttons in the OUT position.
  437.  
  438.     [2]  Choose a N,S,E,W clock that does not already have the
  439.          same time as M (i.e. not aligned with M).
  440.  
  441.     [3]  Push in the closest two buttons to the clock you chose in [2].
  442.  
  443.     [4]  Using the knobs that are farest away from the clock you chose in
  444.          [2] rotate the knob until M and the clock you chose are aligned.
  445.          The time on the clocks at this point does not matter.
  446.  
  447.     [5]  Go back to [1] until N,S,E,W and M are in alignment.
  448.  
  449.     [6]  At this point N,S,E,W and M should all have the same time.
  450.              Make sure all buttons are out and rotate any knob
  451.          until N,S,E,W and M are pointing to 12 oclock.
  452.  
  453. Now turn the puzzle over and repeat steps [1]-[6] for this side.  DO NOT
  454. turn any knobs other than the ones described in [1]-[6].  If you have
  455. done this correctly then on both sides of the puzzle N,S,E,W and M will
  456. all be pointing to 12.
  457.  
  458. Now to align NE,SE,SW,NW.  To finish the puzzle you only need to work from
  459. one side.  Choose a side and use the following algorithm  to align the
  460. corners:
  461.  
  462.     [1]  Start with all buttons OUT on the side you're working from.
  463.         
  464.     [2]  Choose a corner that is not aligned.
  465.  
  466.     [3]  Press the button closest to that corner in.
  467.  
  468.     [4]  Using any knob except for that corner's knob rotate all the
  469.          clocks until they are in line with the corner clock.
  470.          (Here "all the clocks" means N,S,E,W,M and any other clock
  471.          that you have already aligned)
  472.          There is no need at this point to return the clocks to 12
  473.          although if it is less confusing you can.  Remember to
  474.          return all buttons to their up position before you do so.
  475.     
  476.     [5]  Return to [1] until all clocks are aligned.
  477.  
  478.     [6]  With all buttons up rotate all the clocks to 12.
  479.  
  480. ==> games/rubiks.cube.p <==
  481. What is known about bounds on solving Rubik's cube?
  482.  
  483. ==> games/rubiks.cube.s <==
  484. The "official" world record was set by Minh Thai at the 1982 World
  485. Championships in Budapest Hungary, with a time of 22.95 seconds.
  486.  
  487. Keep in mind mathematicians provided standardized dislocation patterns
  488. for the cubes to be randomized as much as possible.
  489.  
  490. The fastest cube solvers from 19 different countries had 3 attempts each
  491. to solve the cube as quickly as possible.   Minh and several others have
  492. unofficially solved the cube in times between 16 and 19 seconds.
  493. However, Minh averages around 25 to 26 seconds after 10 trials, and by
  494. best average of ten trials is about 27 seconds (although it is usually
  495. higher).
  496.  
  497. Consider that in the World Championships 19 of the world's fastest cube
  498. solvers each solved the cube 3 times and no one solved the cube in less
  499. than 20 seconds...
  500.  
  501. God's algorithm is the name given to an as yet (as far as I know)
  502. undiscovered method to solve the rubik's cube in the least number of moves;
  503. as apposed to using 'canned' moves.
  504.  
  505. The known lower bound is 18 moves. This is established by looking at things
  506. backwards: suppose we can solve a position in N moves. Then by running the
  507. solution backwards, we can also go from the solved position to the position
  508. we started with in N moves. Now we count how many sequences of N moves there
  509. are from the starting position, making certain that we don't turn the same
  510. face twice in a row:
  511.  
  512.   N=0: 1 (empty) sequence;
  513.   N=1: 18 sequences (6 faces can be turned, each in 3 different ways)
  514.   N=2: 18*15 sequences (take any sequence of length 1, then turn any of the
  515.        five faces which is not the last face turned, in any of 3 different
  516.        ways);
  517.   N=3: 18*15*15 sequences (take any sequence of length 2, then turn any of
  518.        the five faces which is not the last face turned, in any of 3
  519.        different ways);
  520.   :
  521.   :
  522.   N=i: 18*15^(i-1) sequences.
  523.  
  524. So there are only 1 + 18 + 18*15 + 18*15^2 + ... + 18*15^(n-1) sequences of
  525. moves of length n or less. This sequence sums to (18/14)*(15^n - 1) + 1.
  526. Trying particular values of n, we find that there are about 8.4 * 10^18
  527. sequences of length 16 or less, and about 1.3 times 10^20 sequences of
  528. length 17 or less.
  529.  
  530. Since there are 2^10 * 3^7 * 8! * 12!, or about 4.3 * 10^19, possible
  531. positions of the cube, we see that there simply aren't enough sequences of
  532. length 16 or less to reach every position from the starting position. So not
  533. every position can be solved in 16 or less moves - i.e. some positions
  534. require at least 17 moves.
  535.  
  536. This can be improved to 18 moves by being a bit more careful about counting
  537. sequences which produce the same position. To do this, note that if you turn
  538. one face and then turn the opposite face, you get exactly the same result as
  539. if you'd done the two moves in the opposite order. When counting the number
  540. of essentially different sequences of N moves, therefore, we can split into
  541. two cases:
  542.  
  543. (a) Last two moves were not of opposite faces. All such sequences can be
  544.     obtained by taking a sequence of length N-1, choosing one of the 4 faces
  545.     which is neither the face which was last turned nor the face opposite
  546.     it, and choosing one of 3 possible ways to turn it. (If N=1, so that the
  547.     sequence of length N-1 is empty and doesn't have a last move, we can
  548.     choose any of the 6 faces.)
  549.  
  550. (b) Last two moves were of opposite faces. All such sequences can be
  551.     obtained by taking a sequence of length N-2, choosing one of the 2
  552.     opposite face pairs that doesn't include the last face turned, and
  553.     turning each of the two faces in this pair (3*3 possibilities for how it
  554.     was turned). (If N=2, so that the sequence of length N-2 is empty and
  555.     doesn't have a last move, we can choose any of the 3 opposite face
  556.     pairs.)
  557.  
  558. This gives us a recurrence relation for the number X_N of sequences of
  559. length N:
  560.  
  561.   N=0: X_0                               = 1 (the empty sequence)
  562.   N=1: X_1 = 18 * X_0                    = 18
  563.   N=2: X_2 = 12 * X_1     + 27 * X_0     = 243
  564.   N=3: X_3 = 12 * X_2     + 18 * X_1     = 3240
  565.   :
  566.   :
  567.   N=i: X_i = 12 * X_(i-1) + 18 * X_(i-2)
  568.  
  569. If you do the calculations, you find that X_0 + X_1 + X_2 + ... + X_17 is
  570. about 2.0 * 10^19. So there are fewer essentially different sequences of
  571. moves of length 17 or less than there are positions of the cube, and so some
  572. positions require at least 18 moves.
  573.  
  574. The upper bound of 50 moves is I believe due to Morwen Thistlethwaite, who
  575. developed a technique to solve the cube in a maximum of 50 moves. It
  576. involved a descent through a chain of subgroups of the full cube group,
  577. starting with the full cube group and ending with the trivial subgroup (i.e.
  578. the one containing the solved position only). Each stage involves a careful
  579. examination of the cube, essentially to work out which coset of the target
  580. subgroup it is in, followed by a table look-up to find a sequence to put it
  581. into that subgroup. Needless to say, it was not a fast technique!
  582.  
  583. But it was fascinating to watch, because for the first three quarters or so
  584. of the solution, you couldn't really see anything happening - i.e. the
  585. position continued to appear random! If I remember correctly, one of the
  586. final subgroups in the chain was the subgroup generated by all the double
  587. twists of the faces - so near the end of the solution, you would suddenly
  588. notice that each face only had two colours on it. A few moves more and the
  589. solution was complete. Completely different from most cube solutions, in
  590. which you gradually see order return to chaos: with Morwen's solution, the
  591. order only re-appeared in the last 10-15 moves.
  592.  
  593. With God's algorithm, of course, I would expect this effect to be even more
  594. pronounced: someone solving the cube with God's algorithm would probably
  595. look very much like a film of someone scrambling the cube, run in reverse!
  596.  
  597. Finally, something I'd be curious to know in this context: consider the
  598. position in which every cubelet is in the right position, all the corner
  599. cubelets are in the correct orientation, and all the edge cubelets are
  600. "flipped" (i.e. the only change from the solved position is that every edge
  601. is flipped). What is the shortest sequence of moves known to get the cube
  602. into this position, or equivalently to solve it from this position? (I know
  603. of several sequences of 24 moves that do the trick.)
  604.  
  605. The reason I'm interested in this particular position: it is the unique
  606. element of the centre of the cube group. As a consequence, I vaguely suspect
  607. (I'd hardly like to call it a conjecture :-) it may lie "opposite" the
  608. solved position in the cube graph - i.e. the graph with a vertex for each
  609. position of the cube and edges connecting positions that can be transformed
  610. into each other with a single move. If this is the case, then it is a good
  611. candidate to require the maximum possible number of moves in God's
  612. algorithm.
  613.  
  614.     -- David Seal dseal@armltd.co.uk
  615.  
  616. To my knowledge, no one has ever demonstrated a specific cube position
  617. that takes 15 moves to solve.  Furthermore, the lower bound is known to
  618. be greater than 15, due to a simple proof.
  619.  
  620. The way we know the lower bound is by working backwards counting how
  621. many positions we can reach in a small number of moves from the solved
  622. position.  If this is less than 43,252,003,274,489,856,000 (the total
  623. number of positions of Rubik's cube) then you need more than that
  624. number of moves to reach the other positions of the cube.  Therefore,
  625. those positions will require more moves to solve.
  626.  
  627. The answer depends on what we consider a move.  There are three common
  628. definitions.  The most restrictive is the QF metric, in which only a
  629. quarter-turn of a face is allowed as a single move.  More common is
  630. the HF metric, in which a half-turn of a face is also counted as a
  631. single move.  The most generous is the HS metric, in which a quarter-
  632. turn or half-turn of a central slice is also counted as a single move.
  633. These metrics are sometimes called the 12-generator, 18-generator, and
  634. 27-generator metrics, respectively, for the number of primitive moves.
  635. The definition does not affect which positions you can get to, or even
  636. how you get there, only how many moves we count for it.
  637.  
  638. The answer is that even in the HS metric, the lower bound is 16,
  639. because at most 17,508,850,688,971,332,784 positions can be reached
  640. within 15 HS moves.  In the HF metric, the lower bound is 18, because
  641. at most 19,973,266,111,335,481,264 positions can be reached within 17
  642. HF moves.  And in the QT metric, the lower bound is 21, because at
  643. most 39,812,499,178,877,773,072 positions can be reached within 20 QT
  644. moves.
  645.  
  646.     -- jjfink@skcla.monsanto.com writes:
  647.  
  648.  
  649. Lately in this conference I've noted several messages related to Rubik's
  650. Cube and Square 1. I've been an avid cube fanatic since 1981 and I've
  651. been gathering cube information since.
  652.  
  653. Around Feb. 1990 I started to produce the Domain of the Cube Newsletter,
  654. which focuses on Rubik's Cube and all the cube variants produced to
  655. date. I include notes on unproduced prototype cubes which don't even
  656. exist, patent information, cube history (and prehistory), computer
  657. simulations of puzzles, etc. I'm up to the 4th issue.
  658.  
  659. Anyways, if you're interested in other puzzles of the scramble by
  660. rotation type you may be interested in DOTC. It's available free to
  661. anyone interested. I am especially interested in contributing articles
  662. for the newsletter, e.g. ideas for new variants, God's Algorithm.
  663.  
  664. Anyone ever write a Magic Dodecahedron simulation for a computer? Anyone
  665. understand Morwen Thistlethwaite's 50 move solution to Rubik's Cube? I'd
  666. love to hear from you.
  667.  
  668. Drop me a SASE (say empire size) if you're interested in DOTC or if you
  669. would like to exchange notes on Rubik's Cube, Square 1 etc.
  670.  
  671. I'm also interested in exchanging puzzle simulations, e.g. Rubik's Cube,
  672. Twisty Torus, NxNxN Simulations, etc, for Amiga and IBM computers. I've
  673. written several Rubik's Cube solving programs, and I'm trying to make
  674. the definitive puzzle solving engine. I'm also interested in AI programs
  675. for Rubik's Cube and the like.
  676.  
  677. Ideal Toy put out the Rubik's Cube Newsletter, starting with
  678. issue #1 on May 1982. There were 4 issues in all, and I'm missing
  679. #3.
  680.  
  681. I have:    #1, May 1982
  682.            #2, Aug 1982
  683.            #3, Aug 1983
  684.  
  685. I am willing to trade photocopies with anyone to obtain #3.
  686.  
  687. There was another sort of magazine, published in several languages
  688. called Rubik's Logic and Fantasy in space. I believe there were 8
  689. issues in all. Unfortunately I don't have any of these! I'm willing
  690. to buy these off anyone interesting in selling. I would like to get the
  691. originals if at all possible...
  692.  
  693. I'm also interested in buying any books on the cube or related puzzles.
  694. In particular I am _very_ interested in obtaining the following:
  695.  
  696. Cube Games                               Don Taylor, Leanne Rylands
  697. Official Solution to Alexander's Star    Adam Alexander
  698. The Amazing Pyraminx                     Dr. Ronald Turner-Smith
  699. The Winning Solution                     Minh Thai
  700. The Winning Solution to Rubik's Revenge  Minh Thai
  701. Simple Solutions to Cubic Puzzles        James G. Nourse
  702.  
  703. I'm also interested in buying puzzles of the mechanical type.
  704. I'm still missing the Pyraminx Star (basically a Pyraminx with more tips
  705. on it), the Puck, and Hungarian Rings.
  706.  
  707. If anyone out here is a fellow collector I'd like to hear from you.
  708. If you have a cube variant which you think is rare, or an idea for a
  709. cube variant we could swap notes.
  710.  
  711. I'm in the middle of compiling an exhaustive library for computer
  712. simulations of puzzles. This includes simulations of all Uwe Meffert's
  713. puzzles which he prototyped but _never_ produced. In fact, I'm in the
  714. middle of working on a Pyraminx Hexagon solver. What? Never heard of it?
  715. Meffert did a lot of other puzzles which never were made.
  716.